package com.fanshuai.algorithms.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 装在问题 0-1背包问题的特例，物品价值为1
 * 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。
 * 最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船
 */
public class Load {
    public static int load(Double[] w, double c) {
        //按重量升序排列
        Arrays.sort(w, new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                return Double.compare(o1, o2);
            }
        });

        int maxNum = 0;
        double W = c;
        int j = 0;
        while (W >= w[j]) {
            maxNum += 1;
            W -= w[j];
            j++;
        }

        return maxNum;
    }

    public static void main(String[] args) {
        Double[] w = {2.0, 3.0, 4.0, 5.0, 1.0};
        System.out.println(load(w, 8));
        System.out.println(load(w, 9));
        System.out.println(load(w, 10));
        System.out.println(load(w, 11));
    }
}
